Having established the crucial role of the Order of Growth in efficiency, we now apply this concept to the classic problem of searching.
- The Search Problem is the task of finding the index $i$ of a target value $t$ within an input array $A$ of size $n$.
- The most straightforward method is Linear Search, which sequentially inspects every element $A[i]$ until $t$ is found or the array ends.
- The algorithm iterates from index $i=0$ to $n-1$, comparing the current element $A[i]$ against the target value $t$ at each step.
- The worst-case scenario occurs if the target is the last element or not present at all, requiring the algorithm to perform $n$ comparisons.
- This linear dependency on the input size $n$ gives Linear Search a time complexity of $O(n)$.
Linear Search Properties
| Property | Description | Complexity |
|---|---|---|
| Time (Worst) | Target is last or not present. | $O(n)$ |
| Time (Best) | Target is the first element. | $O(1)$ |
| Space | Requires constant extra space. | $O(1)$ |